A simple coding scheme would encode all symbol values with the same number of bits. The minimum required number of bits per value is log2(nv), where nv is the number of possible values a symbol can take. The average number of bits over all values is therefore also log2(nv).
A more efficient coding scheme encodes symbol values that are expected to occur more frequently with fewer bits, and symbol values that are expected to occur less frequently with more bits. There are a number of ways to do this, but for illustration one way is to let the number of leading zeros in the encoded symbol indicate the length of the encoded symbol. Different possible symbol values v are then mapped to the different length symbol codes c, e.g.:
Code numberSymbol code (c)Maps to symbol value (v)01va1010vb2011vc300100vd400101ve500110vf 600111vg70001000vh80001001vi etc . . .etc . . .etc . . .
The encoder and decoder both have a pre-stored copy of this VLC look-up table. So if the decoder receives a 1 as the first bit of an encoded symbol, it knows this is a one-bit encoded symbol representing code number 0, which maps to symbol value va. If the decoder receives one leading 0 before receiving the first 1, it knows this is a three-bit encoded symbol representing code number 1 or 2 depending on the third bit, which map to symbol values vb and vc respectively. If the decoder receives two leading 0s before receiving the first 1, it knows this is a five-bit encoded symbol representing one of code numbers 3 to 6 depending on the fourth and fifth bits, which map to symbol values vd to vg respectively; and so forth.
This is an example of a set of “prefix” codes, whereby no shorter code is equal to the prefix of any longer code. As mentioned however, this is only one example given for illustrative purposes. Other sets of prefix codes are in common use, such as Huffman codes for example. Other types of variable length coding schemes are also possible, such as those not based on this principle of prefixes, or those that are not in themselves uniquely decodable and rely on some additional known constraint on the bitstream in order to decode. Another type of variable length encoding is arithmetic encoding, which does not map each symbol value onto an individual respective code, but instead encodes a group of symbols together with one overall code.
Such variable length schemes result in a lower average number of bits over all values, compared to assigning the same number of bits to all symbol values. The theoretically minimum possible average number of bits is called entropy and is defined as H=−Σi(pi·log2(pi)), where pi is the probability of the ith symbol value. Therefore such a coding scheme is sometimes called an entropy coder.
Entropy coding relies on availability of some information regarding the relative probabilities of symbol values. Such information may be referred to as the “probability mass function” (PMF), i.e. in this case the likely frequency at which the different possible symbol values are expected to occur relative to one another within the bitstream. Information about the PMF is required at both the encoder and the decoder side (the latter is needed for correct decoding). For example, this information may take the form of a VLC look-up table pre-stored at the encoder and encoder, mapping of symbol values v to the different codes c.
For efficient entropy coding, the available PMF should represent the expected frequencies as accurately as possible. To achieve this, the PMF is conventionally pre-trained at the design stage by using a large set of data that represent symbols to be encoded. This “globally” trained PMF is then pre-stored at the encoder and the decoder.
To further increase coding efficiency, the pre-stored PMF is often adapted during the coding and decoding process. In this ease, a small number of predetermined alternative PMFs are pre-trained for different scenarios, and each alternative is pre-stored at both the encoder and decoder. The encoder and decoder then select the relevant PMF for encoding and decoding a current symbol by observing the previously-coded symbol values.
Examples of such adaptive entropy coding schemes are context-adaptive variable length coding (CAVLC) and context-adaptive binary arithmetic coding (CABAC) used in MPEG Video coding. These are currently defined in the H.264 standard of the Joint Video Team (JVT) of the International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC), comprising the Moving Picture Experts Group (MPEG) and International Telecommunications Union Video Coding Experts Group (ITU-T VCEG).
FIG. 1a is a schematic block diagram of a conventional CAVLC video encoder. Each video frame (i.e. the image at each moment in time) is sub-divided into a plurality of smaller blocks. The input signal is first passed through earlier signal processing stages 102 which perform encoding such as intraframe prediction encoding and interframe motionprediction, to achieve an initial compression by exploiting properties of the video content such as correlation between nearby blocks and movement of blocks between frames. The input signal is then passed to an entropy encoder 106 for further compression based on variable length coding (VLC). A handful of different pre-trained PMFs are pre-stored at the entropy encoder 106, in the form of a plurality of predetermined VLC look-up tables each being a potential candidate for encoding a current symbol sn.
To achieve adaption, a global PMF adaptation block 104 is arranged to select an appropriate one of the VLC look-up tables for encoding a symbol sn of the current block. The selection is based on certain previously encoded symbols sm. For example in CAVLC the selection is based on the number of non-zero coefficients in certain previously encoded blocks, and on previously encoded elements in the current block.
A corresponding decoder is illustrated in FIG. 1b. The incoming bit stream is first passed to an entropy decoder 116, then to later stages 112 such as intraframe prediction decoding and interframe motion prediction decoding stages. The same few pre-trained VLC look-up tables as stored at the encoder are also pre-stored at the entropy decoder 116. The decoder also has the same knowledge of the previous symbol values v[sm] as the encoder (because it has already just decoded those symbols). Given this knowledge of previously decoded symbols sm, a global PMF adaption block 114 in the decoder can therefore deterministically ascertain the VLC look-up table that the encoder must have used to encode a current encoded symbol c(v[sn]), and thus control the entropy decoder 116 to decode the current symbol sn accordingly.
CABAC works in a similar manner, but can also apply an additional adaptation by updating the global PMF based on a previously encoded block and previously encoded symbols in the current block. That is, CABAC adapts not only by selecting between pre-stored look-up tables, but also by modifying the pre-stored look-up tables based on previously encoded symbol values. The decoder can determine the same modification to apply to the look-up tables as applied by the encoder, because the decoder has already previously decoded the same symbols that were used to determine that modification at the encoder.